ইউক্লিডিয়ান অ্যালগরিদম হলো দুটি পূর্ণসংখ্যার মধ্যে গসাগু (GCD) বা গরিষ্ঠ সাধারণ গুণনীয়ক বের করার একটি দক্ষ পদ্ধতি। এটি প্রাচীন গ্রীক গণিতবিদ ইউক্লিড দ্বারা উদ্ভাবিত একটি প্রক্রিয়া, যা পূর্ণসংখ্যাগুলির বিভাজক নির্ধারণে গুরুত্বপূর্ণ ভূমিকা পালন করে। অ্যালগরিদমটি মূলত সংখ্যা দুটি একে অপরের সাথে ভাগ করে গুণনীয়ক বের করে এবং শেষ পর্যন্ত শূন্য অবশিষ্টাংশ পাওয়া যায় এমন একটি সংখ্যা নির্ধারণ করে, যেটি GCD হয়।
ইউক্লিডিয়ান অ্যালগরিদমের ধাপসমূহ:
- দুটি সংখ্যা \( a \) এবং \( b \) নিন, যেখানে \( a > b \)।
- \( a \) কে \( b \) দ্বারা ভাগ করুন এবং ভাগশেষ বের করুন, অর্থাৎ \( r = a \mod b \)।
- যদি \( r = 0 \) হয়, তবে \( b \) হলো \( a \) এবং \( b \)-এর গসাগু (GCD)।
- যদি \( r \neq 0 \) হয়, তাহলে \( a = b \) এবং \( b = r \) নিন এবং আবার ধাপ ২ থেকে প্রক্রিয়া চালিয়ে যান।
- প্রক্রিয়াটি চলতে থাকবে যতক্ষণ না অবশিষ্টাংশ ০ হয়, এবং তখনকার \( b \)-এর মানই গসাগু হবে।
উদাহরণ
ধরি, \( a = 56 \) এবং \( b = 98 \)।
- \( 98 \mod 56 = 42 \)
- \( 56 \mod 42 = 14 \)
- \( 42 \mod 14 = 0 \)
এখানে শেষ ভাগশেষ ০ পাওয়া গেছে, সুতরাং \( GCD(56, 98) = 14 \)।
ইউক্লিডিয়ান অ্যালগরিদমটি সংখ্যাতত্ত্ব, ক্রিপ্টোগ্রাফি, এবং গাণিতিক সমীকরণ সমাধানে ব্যাপকভাবে ব্যবহৃত হয়।
গসিয়ান এলিমিনেশন (Gaussian Elimination)
গসিয়ান এলিমিনেশন হলো একটি অ্যালগরিদম যা একাধিক চলকের সাথে গাণিতিক সমীকরণের একটি লিনিয়ার সিস্টেম সমাধানের জন্য ব্যবহৃত হয়। এই প্রক্রিয়াটি রো-রিডাকশন নামেও পরিচিত, এবং এর মাধ্যমে সমীকরণগুলোকে ধাপে ধাপে সরল করে একটি সমাধান পাওয়া সম্ভব হয়। এটি মূলত একটি ম্যাট্রিক্সে বিভিন্ন সারি এবং কলামকে ম্যানিপুলেট করে একক ম্যাট্রিক্স বা রিডিউসড রো-একলন ফর্ম (RREF) আকারে নিয়ে আসে, যাতে সহজেই সমীকরণগুলো সমাধান করা যায়।
গসিয়ান এলিমিনেশনের ধাপসমূহ:
- একটি লিনিয়ার সিস্টেমকে ম্যাট্রিক্স আকারে প্রকাশ করুন।
- প্রথম কলামে প্রথম পিভট এলিমেন্ট (pivot element) নির্ধারণ করুন এবং অন্যান্য রো থেকে পিভট এলিমেন্ট সরিয়ে ফেলুন, যাতে ঐ কলামের নিচের সব এলিমেন্ট ০ হয়।
- পরবর্তী কলামের জন্য একই প্রক্রিয়া পুনরাবৃত্তি করুন।
- ধাপে ধাপে এলিমিনেশন চালিয়ে যান যতক্ষণ না ম্যাট্রিক্সটি একক ম্যাট্রিক্স বা এর কাছাকাছি আকারে চলে আসে।
- একবার ম্যাট্রিক্স RREF আকারে এলে প্রত্যেক চলক বা ভ্যারিয়েবলকে একটি সমাধানে নির্ধারণ করা যায়।
উদাহরণ
ধরি, নিচের সমীকরণ সিস্টেমটি সমাধান করতে হবে:
\[
x + y + z = 6
\]
\[
2y + 5z = -4
\]
\[
2x + 5y - z = 27
\]
এটি গসিয়ান এলিমিনেশন ব্যবহার করে সমাধান করা সম্ভব, তবে সমীকরণগুলোকে একটি অগমেন্টেড ম্যাট্রিক্সে প্রকাশ করে ধাপে ধাপে সরলীকরণ করতে হবে। এই প্রক্রিয়ার মাধ্যমে প্রতিটি চলকের জন্য একটি নির্দিষ্ট মান নির্ধারণ করা যায়।
গসিয়ান এলিমিনেশন অ্যালজেব্রার বিভিন্ন সমস্যার সমাধানে গুরুত্বপূর্ণ ভূমিকা পালন করে, বিশেষত যখন একটি লিনিয়ার সিস্টেমের একাধিক সমাধান বের করতে হয়।
Read more
